
str1="algorithm"
str2="alligator"

str1="-"+str1+"-"
str2="-"+str2+"-"
X,Y=len(str1),len(str2)
cost_array=[[0 for _ in range(Y)]for _ in range(X)]

operation =[[False for _ in range(Y)]for _ in range(X)]

def cost(a,b):
    if a == b:
        return 0
    else:
        return 5

for i in range(X): # 填表
    for j in range(Y):
        if i == 0 and j == 0 :
            cost_array[i][j] = 0
        elif i == 0:
            cost_array[i][j] = cost_array[i][j-1]+20
            operation[i][j]=(i,j-1)
        elif j == 0:
            cost_array[i][j] = cost_array[i-1][j]+20
            operation[i][j]=(i-1,j)
        else:
            costLT=cost_array[i-1][j-1]+cost(str1[i],str2[j])
            costT=cost_array[i-1][j]+20
            costL=cost_array[i][j-1]+20
            cost_array[i][j]=min(costLT,costL,costT)
            if cost_array[i][j]==costLT:
                operation[i][j]=(i-1,j-1)
            elif cost_array[i][j]==costT:
                operation[i][j]=(i-1,j)
            else:
                operation[i][j]=(i,j-1)


operator=list()
i,j = (X-1,Y-1)
while True : # 回溯
    if not operation[i][j]:
        break
    toi,toj = operation[i][j]
    if toi == i:
        operator.append(f"add\t{str2[j]}\t20")
    elif toj == j:
        operator.append(f"{str1[i]}\tdelate\t20")
    elif str1[i]==str2[j]:
        if str1[i]!="-":
            operator.append(f"{str1[i]}\t{str2[j]}\t0")
    else:
        operator.append(f"{str1[i]}\t{str2[j]}\t5")
    i,j=toi,toj


print(f"{str1[1:-1]}到{str2[1:-1]}的最短编辑距离：{cost_array[i][j]}")
print("编辑策略：")
print(f"from\tto\tcost")
for line in operator[::-1]:
    print(line)
